\section{Sushi}
\subsection*{题意}
现在有 $n$ 盘寿司在桌上排成一排，第 $i$ 盘寿司里面有 $a_i$ 个寿司。直到吃完所有寿司为止，你都会持续进行下述操作：
\begin{itemize}
\item 从 $\{1,2,\cdots,n\}$ 中\textbf{均匀随机}选取一个数 $i$。如果第 $i$ 盘中仍有寿司，那就吃一块，否则什么也不做。
\end{itemize}

现在求期望操作次数是多少。

\subsection*{数据范围}
\begin{itemize}
\item $1 \leq n \leq 300$
\item $1 \leq a_i \leq 3$
\end{itemize}

\subsection*{题解}

\subsubsection*{暴力DP}
首先我们考虑最暴力的做法，用 ${\texttt{dp}}[c_1][c_2]\cdots[c_n]$ 表示第$i$盘还剩$c_i$个寿司的期望次数。那么枚举随机到的数 $i$ 就可以得到方程：
$$
{\texttt{dp}}[c_1][c_2]\cdots[c_n] = 1+\sum_{i = 1}^n \frac{1}{n }{\texttt{dp}}[c_1][c_2]\cdots[\max(c_i-1,0)]\cdots[c_n]
$$

\subsubsection*{合并状态}
（注意该方程并不能构成\textbf{转移}方程，因为当第 $i$ 盘已经为空的时候，状态不变）

我们现在考虑\textbf{合并等价状态}（题外话：动态规划优化的初等方法无非就那么几种，合并状态就是最重要的思想之一）。

注意到由于随机数是均匀选取的，那么盘子的位置是无关紧要的，而只有剩余数量有影响。于是相同数值的不同排列的期望次数必然是相同的。例如${\texttt{dp}}[1][2][3] = {\texttt{dp}}[3][2][1]$。

所以只需要考虑每种数值出现的次数。因为 $a_i \le 3$，所以至多有四种不同数值：$\{0,1,2,3\}$。我们重新定义状态 ${\texttt{dp}[a][b][c][d]}$ 表示当前还剩下
$a/b/c/d$ 盘有$0/1/2/3$个寿司。

有了状态，我们通过枚举当前随机到的盘子里还剩几只寿司得到如下方程：
\begin{align*}
{\texttt{dp}[a][b][c][d]}
= 1
+&\frac{a}{n} {\texttt{dp}[a][b][c][d]}\\
+&\frac{b}{n} {\texttt{dp}[a+1][b-1][c][d]} \\
+&\frac{c}{n} {\texttt{dp}[a][b+1][c-1][d]} \\
+&\frac{d}{n} {\texttt{dp}[a][b][c+1][d-1]} 
\end{align*}

移项整理得到\textbf{转移}方程：
\begin{align*}
{\texttt{dp}[a][b][c][d]}
= &\frac{n}{b+c+d}\\
+&\frac{b}{b+c+d} {\texttt{dp}[a+1][b-1][c][d]} \\
+&\frac{c}{b+c+d} {\texttt{dp}[a][b+1][c-1][d]} \\
+&\frac{d}{b+c+d} {\texttt{dp}[a][b][c+1][d-1]} 
\end{align*}

\subsubsection*{消除无用状态}
但由于 $n\le 300$，总状态数高达 $300^4 \approx 8\times 10^9$ 无法通过。我们需要进一步优化。

注意到任意时刻下，$a+b+c+d$ 的值都应该等于 $n$：因为不管进行多少次操作，盘子总数总是 $n$。所以其实只需要知道 $b,c,d$就可以反推出$a$的值：$a = n-(b+c+d)$。那么现在只保留后面三维，得到转移方程：
\begin{align*}
{\texttt{dp}[b][c][d]} 
= &\frac{n}{b+c+d}\\
+&\frac{b}{b+c+d} {\texttt{dp}[b-1][c][d]} \\
+&\frac{c}{b+c+d} {\texttt{dp}[b+1][c-1][d]} \\
+&\frac{d}{b+c+d} {\texttt{dp}[b][c+1][d-1]} 
\end{align*}

至此，足矣。

\newpage
\subsection*{核心代码}
\inputminted[linenos,autogobble]{cpp}{./Code/J.cpp}
\newpage